In order to protect privacy of consumers in cloud computing, encrypted data storage is a feasible way. To speed up process of encryption and decryption, a parallel Advanced Encryption Standard (AES) encryption algorithm was proposed taking the characteristic of multi-nodes in cloud computing into account. The performance of the algorithm was analyzed in theory, and then experiments were conducted to demonstrate the efficiency of the designed algorithm. The experimental results show that the speed-up radio of the proposed encryption scheme can reach 15.9, and the total time cost of AES encryption can be reduced by 72.7% on the cloud cluster consisting of 4 compute nodes of total 16 CPUs.